package ninthweek;

import eighthweek.BinaryTreeADT;
import fourthweek.Array.ArrayUnorderedList;
import fourthweek.ElementNotFoundException;
import secondweek.EmptyCollectionException;
import seventhweek.BinaryTreeNode;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedBinaryTree<T> implements BinaryTreeADT<T>, Iterable<T>
{
    protected BinaryTreeNode<T> root;
    protected int modCount;
    protected LinkedBinaryTree<T> left,right;


    public LinkedBinaryTree()
    {
        root = null;
    }


    public LinkedBinaryTree(T element)
    {
        root = new BinaryTreeNode<T>(element);
    }


    public LinkedBinaryTree(T element, LinkedBinaryTree<T> left,
                            LinkedBinaryTree<T> right)
    {
        root = new BinaryTreeNode<T>(element);
        root.setLeft(left.root);
        root.setRight(right.root);
        this.left = left;
        this.right = right;
    }


    public T getRootElement() throws EmptyCollectionException
    {
        if (root.getElement().equals(null)) {
            throw new EmptyCollectionException("BinaryTreeNode ");
        }
        return root.getElement();
    }


    public BinaryTreeNode<T> getRootNode() throws EmptyCollectionException
    {

        if (isEmpty()) {
            throw new EmptyCollectionException("BinaryTreeNode ");
        }
        return root;
    }


    public LinkedBinaryTree<T> getLeft()
    {
        return left;
    }


    public LinkedBinaryTree<T> getRight()
    {
        return right;
    }


    public boolean isEmpty()
    {
        return (root == null);
    }


    public int size()
    {
        return root.numChildren() + 1;
    }


    public int getHeight()
    {
        return height(root);
    }


    private int height(BinaryTreeNode<T> node)
    {
        if(node==null){
            return 0;
        }
        else {
            int leftTreeHeight = height(node.getLeft());
            int rightTreeHeight= height(node.getRight());
            return leftTreeHeight>rightTreeHeight ? (leftTreeHeight+1):(rightTreeHeight+1);
        }
    }

    public boolean contains(T targetElement)
    {
        boolean result = contains(targetElement, root);
        return result;
    }
    private boolean contains(T targetElement,
                             BinaryTreeNode<T> next)
    {
        if (next == null)
            return false;

        if (String.valueOf(next.getElement()).equals(String.valueOf(targetElement)))
            return true;

        Boolean temp = contains(targetElement, next.getLeft());

        if (temp == null)
            temp = contains(targetElement, next.getRight());

        return temp;
    }


    public T find(T targetElement) throws ElementNotFoundException
    {
        BinaryTreeNode<T> current = findNode(targetElement, root);

        if (current == null)
            throw new ElementNotFoundException("LinkedBinaryTree");

        return (current.getElement());
    }


    private BinaryTreeNode<T> findNode(T targetElement,
                                       BinaryTreeNode<T> next)
    {
        if (next == null)
            return null;

        if (next.getElement().equals(targetElement))
            return next;

        BinaryTreeNode<T> temp = findNode(targetElement, next.getLeft());

        if (temp == null)
            temp = findNode(targetElement, next.getRight());

        return temp;
    }

    public void removeRightSubtree()
    {

    }

    public void removeAllElements()
    {
        root = null;
    }


    public String toString()
    {
        Iterator<T> iterator = iteratorInOrder();
        return iterator.toString();

    }


    public Iterator<T> iterator()
    {
        return iteratorInOrder();
    }


    public Iterator<T> iteratorInOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        inOrder(root, tempList);

        return new TreeIterator(tempList.iterator());
    }


    protected void inOrder(BinaryTreeNode<T> node,
                           ArrayUnorderedList<T> tempList)
    {
        if (node != null)
        {
            inOrder(node.getLeft(), tempList);
            tempList.addToRear(node.getElement());
            inOrder(node.getRight(), tempList);
        }
    }


    public Iterator<T> iteratorPreOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        preOrder(root, tempList);

        return new TreeIterator(tempList.iterator());
    }


    protected void preOrder(BinaryTreeNode<T> node,
                            ArrayUnorderedList<T> tempList)
    {
        if (node != null)
        {
            tempList.addToRear(node.getElement());
            inOrder(node.getLeft(), tempList);
            inOrder(node.getRight(), tempList);
        }
    }


    public Iterator<T> iteratorPostOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        postOrder(root, tempList);

        return new TreeIterator(tempList.iterator());
    }


    protected void postOrder(BinaryTreeNode<T> node,
                             ArrayUnorderedList<T> tempList)
    {
        if (node != null)
        {
            inOrder(node.getLeft(), tempList);
            inOrder(node.getRight(), tempList);
            tempList.addToRear(node.getElement());
        }
    }


    public Iterator<T> iteratorLevelOrder()
    {
        ArrayUnorderedList<BinaryTreeNode<T>> nodes =
                new ArrayUnorderedList<BinaryTreeNode<T>>();
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        BinaryTreeNode<T> current;

        nodes.addToRear(root);

        while (!nodes.isEmpty())
        {
            current = nodes.removeFirst();

            if (current != null)
            {
                tempList.addToRear(current.getElement());
                if (current.getLeft() != null)
                    nodes.addToRear(current.getLeft());
                if (current.getRight() != null)
                    nodes.addToRear(current.getRight());
            }
            else
                tempList.addToRear(null);
        }

        return new TreeIterator(tempList.iterator());
    }

    /**
     * Inner class to represent an iterator over the elements of this tree
     */
    private class TreeIterator implements Iterator<T>
    {
        private int expectedModCount;
        private Iterator<T> iter;


        public TreeIterator(Iterator<T> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }


        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();

            return (iter.hasNext());
        }


        public T next() throws NoSuchElementException
        {
            if (hasNext())
                return (iter.next());
            else
                throw new NoSuchElementException();
        }

        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }
}
